{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Two Polynomials Represented as Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #math #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #数学 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addPoly"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求两个多项式链表的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>多项式链表是一种特殊形式的链表，每个节点表示多项式的一项。</p>\n",
    "\n",
    "<p>每个节点有三个属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>coefficient</code>：该项的系数。项 <code><strong>9</strong>x<sup>4</sup></code> 的系数是 <code>9</code> 。</li>\n",
    "\t<li><code>power</code>：该项的指数。项 <code>9x<strong><sup>4</sup></strong></code> 的指数是 <code>4</code> 。</li>\n",
    "\t<li><code>next</code>：指向下一个节点的指针（引用），如果当前节点为链表的最后一个节点则为 <code>null</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，多项式 <code>5x<sup>3</sup> + 4x - 7</code> 可以表示成如下图所示的多项式链表：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/30/polynomial2.png\" style=\"width: 500px; height: 91px;\" /></p>\n",
    "\n",
    "<p>多项式链表必须是标准形式的，即多项式必须<strong> 严格 </strong>按指数 <code>power</code> 的递减顺序排列（即降幂排列）。另外，系数 <code>coefficient</code> 为 <code>0</code> 的项需要省略。</p>\n",
    "\n",
    "<p>给定两个多项式链表的头节点 <code>poly1</code> 和 <code>poly2</code>，返回它们的和的头节点。</p>\n",
    "\n",
    "<p><strong><code>PolyNode</code> 格式：</strong></p>\n",
    "\n",
    "<p>输入/输出格式表示为 <code>n</code> 个节点的列表，其中每个节点表示为 <code>[coefficient, power]</code> 。例如，多项式 <code>5x<sup>3</sup> + 4x - 7</code> 表示为： <code>[[5,3],[4,1],[-7,0]]</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/14/ex1.png\" style=\"width: 600px; height: 322px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>poly1 = [[1,1]], poly2 = [[1,0]]\n",
    "<strong>输出：</strong>[[1,1],[1,0]]\n",
    "<strong>解释：</strong>poly1 = x. poly2 = 1. 和为 x + 1.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]\n",
    "<strong>输出：</strong>[[5,2],[2,0]]\n",
    "<strong>解释：</strong>poly1 = 2x<sup>2</sup> + 4x + 3. poly2 = 3x<sup>2</sup> - 4x - 1. 和为 5x<sup>2</sup> + 2. 注意，我们省略 \"0x\" 项。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>poly1 = [[1,2]], poly2 = [[-1,2]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>和为 0。我们返回空链表。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= PolyNode.coefficient <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>PolyNode.coefficient != 0</code></li>\n",
    "\t<li><code>0 <= PolyNode.power <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>PolyNode.power > PolyNode.next.power</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-two-polynomials-represented-as-linked-lists](https://leetcode.cn/problems/add-two-polynomials-represented-as-linked-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-two-polynomials-represented-as-linked-lists](https://leetcode.cn/problems/add-two-polynomials-represented-as-linked-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1]]\\n[[1,0]]', '[[2,2],[4,1],[3,0]]\\n[[3,2],[-4,1],[-1,0]]', '[[1,2]]\\n[[-1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "class PolyNode:\n",
    "    def __init__(self, x=0, y=0, next=None):\n",
    "        self.coefficient = x\n",
    "        self.power = y\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "\n",
    "        head=PolyNode()\n",
    "        node=head\n",
    "\n",
    "        while poly1!=None and poly2!=None:\n",
    "            if poly1.power>poly2.power:\n",
    "                node.next=poly1\n",
    "                poly1=poly1.next\n",
    "                node=node.next\n",
    "            elif poly1.power<poly2.power:\n",
    "                node.next=poly2\n",
    "                poly2=poly2.next\n",
    "                node=node.next\n",
    "            else:\n",
    "                n=poly1.coefficient+poly2.coefficient\n",
    "                if n!=0:\n",
    "                    poly1.coefficient=n\n",
    "                    node.next=poly1\n",
    "                    poly1=poly1.next\n",
    "                    poly2=poly2.next\n",
    "                    node=node.next\n",
    "                else:\n",
    "                    poly1=poly1.next\n",
    "                    poly2=poly2.next\n",
    "\n",
    "\n",
    "        if poly1:\n",
    "            node.next=poly1\n",
    "        elif poly2:\n",
    "            node.next=poly2\n",
    "        else:\n",
    "            node.next=None\n",
    "\n",
    "        return head.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "# class PolyNode:\n",
    "#     def __init__(self, x=0, y=0, next=None):\n",
    "#         self.coefficient = x\n",
    "#         self.power = y\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "        if not poly1 and not poly2:\n",
    "            return None\n",
    "        if not poly1:\n",
    "            return poly2\n",
    "        if not poly2:\n",
    "            return poly1\n",
    "        dummy=PolyNode(0)\n",
    "        cur=dummy\n",
    "        while poly1 and poly2:\n",
    "            if poly1.power>poly2.power:\n",
    "                cur.next=poly1\n",
    "                poly1=poly1.next\n",
    "                cur=cur.next\n",
    "            elif poly2.power>poly1.power:\n",
    "                cur.next=poly2\n",
    "                poly2=poly2.next\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                sum=poly1.coefficient+poly2.coefficient\n",
    "                \n",
    "                if sum!=0:\n",
    "                    cur.next=PolyNode(sum,poly1.power)\n",
    "                    cur=cur.next\n",
    "                poly1=poly1.next\n",
    "                poly2=poly2.next                \n",
    "                \n",
    "                        \n",
    "        if not poly1:\n",
    "            cur.next=poly2\n",
    "        if not poly2:\n",
    "            cur.next=poly1\n",
    "        return dummy.next\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "# class PolyNode:\n",
    "#     def __init__(self, x=0, y=0, next=None):\n",
    "#         self.coefficient = x\n",
    "#         self.power = y\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "        dummy = cur = PolyNode()\n",
    "        while poly1 and poly2:\n",
    "            if poly1.power > poly2.power:\n",
    "                cur.next = poly1\n",
    "                poly1 = poly1.next\n",
    "                cur = cur.next\n",
    "            elif poly1.power < poly2.power:\n",
    "                cur.next = poly2\n",
    "                poly2 = poly2.next\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                if (coe := poly1.coefficient + poly2.coefficient) != 0:\n",
    "                    cur.next = PolyNode(coe, poly1.power)\n",
    "                    cur = cur.next \n",
    "                poly1 = poly1.next \n",
    "                poly2 = poly2.next\n",
    "            cur.next = None\n",
    "                \n",
    "        if poly1:\n",
    "            cur.next = poly1\n",
    "        elif poly2:\n",
    "            cur.next = poly2\n",
    "\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "# class PolyNode:\n",
    "#     def __init__(self, x=0, y=0, next=None):\n",
    "#         self.coefficient = x\n",
    "#         self.power = y\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "\n",
    "        ans = PolyNode(-1, -1)\n",
    "        cur = ans\n",
    "        while poly1 and poly2:\n",
    "            if poly1.power > poly2.power:\n",
    "                tmp = poly1.next\n",
    "                poly1.next = None\n",
    "                cur.next = poly1\n",
    "                cur = cur.next\n",
    "                poly1 = tmp\n",
    "            elif poly1.power < poly2.power:\n",
    "                tmp = poly2.next\n",
    "                poly2.next = None\n",
    "                cur.next = poly2\n",
    "                cur = cur.next\n",
    "                poly2 = tmp\n",
    "            else:\n",
    "                if poly1.coefficient + poly2.coefficient:\n",
    "                    cur.next = PolyNode(poly1.coefficient + poly2.coefficient, poly1.power)\n",
    "                    cur = cur.next\n",
    "                poly1 = poly1.next\n",
    "                poly2 = poly2.next\n",
    "\n",
    "        if poly1:\n",
    "            cur.next = poly1\n",
    "        if poly2:\n",
    "            cur.next = poly2\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "# class PolyNode:\n",
    "#     def __init__(self, x=0, y=0, next=None):\n",
    "#         self.coefficient = x\n",
    "#         self.power = y\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "        dic={}\n",
    "        while poly1:\n",
    "            dic[poly1.power]=poly1.coefficient\n",
    "            poly1=poly1.next\n",
    "        while poly2:\n",
    "            if poly2.power not in dic:\n",
    "                dic[poly2.power]=poly2.coefficient\n",
    "            else:\n",
    "                dic[poly2.power]+=poly2.coefficient\n",
    "            poly2=poly2.next\n",
    "        keys=sorted(list(dic.keys()),reverse=True)\n",
    "        head=PolyNode()\n",
    "        current=head\n",
    "        for i in keys:\n",
    "            if dic[i]!=0:\n",
    "                current.next=PolyNode(dic[i],i)\n",
    "                current=current.next\n",
    "        return head.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for polynomial singly-linked list.\n",
    "# class PolyNode:\n",
    "#     def __init__(self, x=0, y=0, next=None):\n",
    "#         self.coefficient = x\n",
    "#         self.power = y\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':\n",
    "        dic = defaultdict(int)\n",
    "        while poly1:\n",
    "            dic[poly1.power] += poly1.coefficient\n",
    "            poly1 = poly1.next\n",
    "        while poly2:\n",
    "            dic[poly2.power] += poly2.coefficient\n",
    "            poly2 = poly2.next\n",
    "        arr = []\n",
    "        for k, v in dic.items():\n",
    "            if v:\n",
    "                arr.append((k, v))\n",
    "        arr.sort(reverse=True)\n",
    "\n",
    "        dummy = PolyNode()\n",
    "        curr = dummy\n",
    "        for k, v in arr:\n",
    "            node = PolyNode(v, k)\n",
    "            curr.next = node\n",
    "            curr = node\n",
    "        return dummy.next\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
